package sort;

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {3,2,1,0,5,7,6,9,8,10};
        insertSort(arr);
        for (int x: arr) {
            System.out.print(x + " ");
        }
    }
    public static void insertSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            //记录待插入元素的下标
            int index = i;
            //待插入元素
            int cur = arr[i];
            //元素移动
            while (index > 0){
                //升序排序，后面的元素小于前面的就往前插入
                if(cur < arr[index - 1]){
                     arr[index] = arr[index - 1];
                    index--;
                }else {
                    break;
                }

            }
            //将待插入元素插入对应位置
            arr[index] = cur;
        }
    }
}
